package 动态规划;

public class No221最大正方形 {

    /**
     * 在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
     *
     * 示例 1：
     * 输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
     * 输出：4
     * 示例 2：
     * 输入：matrix = [["0","1"],["1","0"]]
     * 输出：1
     * 示例 3：
     * 输入：matrix = [["0"]]
     * 输出：0
     *
     * 提示：
     * m == matrix.length
     * n == matrix[i].length
     * 1 <= m, n <= 300
     * matrix[i][j] 为 '0' 或 '1'
     */

    public int maximalSquare(char[][] matrix) {
        if(matrix.length==0||matrix[0].length==0){
            return 0;
        }
        int allLength=matrix.length;
        int itemLength=matrix[0].length;

        int[][] dp=new int[allLength][itemLength];

        int result=0;

        for (int i = 0; i < allLength; i++) {
            if(matrix[i][0]=='1'){
                dp[i][0]=1;
                result=1;
            }
        }
        for (int i = 0; i < itemLength; i++) {
            if(matrix[0][i]=='1'){
                dp[0][i]=1;
                result=1;
            }
        }

        for (int i = 1; i < allLength; i++) {
            for (int j = 1; j < itemLength; j++) {
                if(dp[i-1][j-1]==0||matrix[i][j]=='0'||matrix[i][j-1]=='0'||matrix[i-1][j]=='0'){
                    //左上范围有0,那么只能自成一个小正方形
                    if(matrix[i][j]!='0') {
                        dp[i][j] = 1;
                    }
                }else{
                    /**
                     * 官方参考解法是,取 左,左上+1,上 dp的最小值
                     */
                    //右上范围都不为0,那就要参考 dp[i-1][j-1]
                    int count=dp[i-1][j-1];
                    int minLength=0;//必定大于等于1
                    for (int k = 1; k <= count; k++) {
                        //分别向 左边 和 上边 进行遍历查找,找到能共同探索到的最长位置
                        if(dp[i-k][j]>0&&dp[i][j-k]>0){
                            minLength++;
                        }else{
                            break;
                        }
                    }
                    if(minLength==count){
                        //全吃
                        dp[i][j]=dp[i-1][j-1]+1;
                    }else{
                        //非全吃
                        dp[i][j]=minLength+1;
                    }
                }
                result=Math.max(result,dp[i][j]);
            }
        }

        return result*result;
    }

    public int maximalSquareGood(char[][] matrix) {
        if(matrix.length==0||matrix[0].length==0){
            return 0;
        }
        int allLength=matrix.length;
        int itemLength=matrix[0].length;

        int[][] dp=new int[allLength][itemLength];

        int result=0;

        for (int i = 0; i < allLength; i++) {
            if(matrix[i][0]=='1'){
                dp[i][0]=1;
                result=1;
            }
        }
        for (int i = 0; i < itemLength; i++) {
            if(matrix[0][i]=='1'){
                dp[0][i]=1;
                result=1;
            }
        }

        for (int i = 1; i < allLength; i++) {
            for (int j = 1; j < itemLength; j++) {
                if(matrix[i][j] == '1'){
                    dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1])+1;
                }
                result=Math.max(result,dp[i][j]);
            }
        }

        return result*result;
    }

    public static void main(String[] args) {
        No221最大正方形 n=new No221最大正方形();
        char[][] arr={
                {'0','0','0','1','0','1','1','1'},
                {'0','1','1','0','0','1','0','1'},
                {'1','0','1','1','1','1','0','1'},
                {'0','0','0','1','0','0','0','0'},
                {'0','0','1','0','0','0','1','0'},
                {'1','1','1','0','0','1','1','1'},
                {'1','0','0','1','1','0','0','1'},
                {'0','1','0','0','1','1','0','0'},
                {'1','0','0','1','0','0','0','0'}};
        int result = n.maximalSquare(arr);
        System.out.println(result);
        System.out.println(n.maximalSquareGood(arr));
    }

}
